package 剑指offer;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;

/**
 * Created by root on 17-3-1.
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
 */
public class ConvertBSTAsDLL {
    ArrayList<TreeNode> arrayList = new ArrayList<>();
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return pRootOfTree;
        }
        convert( pRootOfTree);
        return arrayList.get(0);
    }

    public void convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return;
        }
        convert(pRootOfTree.left);
        if (!arrayList.isEmpty()) {
            arrayList.get(arrayList.size() - 1).right = pRootOfTree;
            pRootOfTree.left = arrayList.get(arrayList.size() - 1);
        }
        arrayList.add(pRootOfTree);
        convert(pRootOfTree.right);
    }
}
